class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> hash1;
        for(auto &w:words) hash1[w]++;
        int n=words[0].size(),m=words.size();
        vector<int> ret;
        for(int i=0;i<n;++i)
        {
            unordered_map<string,int> hash2;
            for(int left=i,right=i,cnt=0;right+n<=s.size();right+=n)
            {
                string in=s.substr(right,n);
                hash2[in]++;
                if(hash2[in]<=hash1[in]) ++cnt;
                while(right-left+1>n*m)
                {
                    string out=s.substr(left,n);
                    if(hash2[out]<=hash1[out]) --cnt;
                    --hash2[out];
                    left+=n;
                }
                if(cnt==m) ret.push_back(left);
            }
        }
        return ret;
    }
};
